'''
https://leetcode-cn.com/problems/employee-importance/submissions/
其实是一棵多叉树的层次遍历
唯一不同的是树的子儿子不是树本身 而是id
用一个dic把每个id和对应的树存起来就解决了
'''

from typing import List
from collections import deque


class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates


class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        dic = {}
        for e in employees:
            dic[e.id] = e
        if id not in dic:
            return 0
        root = dic[id]
        res = 0
        queue = deque()
        queue.append(root)
        while queue:
            for _ in range(0, len(queue)):
                root = queue.popleft()
                if root:
                    res += root.importance
                    if root.subordinates:
                        for sub in root.subordinates:
                            queue.append(sub)
        return res
